class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size() == 0) {
            return vector<vector<int> >();
        }
        sort(num.begin(), num.end());
        vector<int> values;
        vector<vector<int> > ans;
        calculateHelper(0, values, target, 0, num, ans);
        return ans;
    }

    void calculateHelper(int curSum, vector<int> &values, int target, int start, const vector<int> &candidates, vector<vector<int> > &ans) {
        int n = candidates.size();
        for (int i = start; i < n; ) {
            values.push_back(candidates[i]);
            if (curSum + candidates[i] == target) {
                ans.push_back(values);
                values.pop_back();
            } else if (curSum + candidates[i] < target) {
                calculateHelper(curSum + candidates[i], values, target, i + 1, candidates, ans);
                values.pop_back();
            } else {
                values.pop_back();
                break;
            }
            int j = i + 1;
            while (j < n && candidates[j] == candidates[i]) {
                ++j;
            }
            i = j;
        }
    }
};
